home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / basic / _tree_collect.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  12.2 KB  |  580 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _tree_collect.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. // dyna_trees.c
  18.  
  19. #include <LEDA/tree_collection.h>
  20.  
  21. #define BIG MAXFLOAT
  22.  
  23.  
  24. void dyna_trees::splay(d_vertex x) {
  25.      d_vertex y, z, zz, a, b, c, d;
  26.      double   mincost_a,
  27.           mincost_b,
  28.           mincost_c,
  29.           mincost_d,
  30.           mincost_x,
  31.           mincost_y,
  32.           mincost_z,
  33.           
  34.           cost_x,
  35.           cost_y,
  36.           cost_z;
  37.  
  38.      
  39.      while (x->parent) {
  40.       // splay-step : 
  41.  
  42.       y=x->parent; // Vater von x
  43.       z=y->parent; // Grossvater von x (oder 0)
  44.       zz = (z==0) ? 0 : z->parent; // Urgrossvater von z (oder 0)
  45.  
  46.       // 1.Fall: x hat Vater, aber keinen Grossvater
  47.  
  48.       if (z==0){ 
  49.         if (y->left==x) { 
  50.             // x wurzel des linken unterbaums  (1)
  51.             a=x->left;
  52.             b=x->right;
  53.             c=y->right;
  54.             x->parent=0;
  55.             x->right=y;
  56.             y->parent=x;
  57.             y->left=b;
  58.             if (b) b->parent=y;
  59.  
  60.             x->successor=y->successor;
  61.             y->successor=0;
  62.  
  63.             mincost_a = (a) ? a->dmin + x->dmin + y->dmin : BIG;
  64.             mincost_b = (b) ? b->dmin + x->dmin + y->dmin : BIG;
  65.             mincost_c = (c) ? c->dmin + y->dmin : BIG;
  66.             mincost_x = x->dmin + y->dmin;
  67.             mincost_y = y->dmin;
  68.             cost_x    = x->dcost + mincost_x;
  69.             cost_y    = y->dcost + mincost_y;
  70.             
  71.             mincost_x = mincost_y;
  72.             mincost_y = (mincost_b <= mincost_c) ? mincost_b : mincost_c;
  73.             if (cost_y <= mincost_y) mincost_y = cost_y;
  74.             x->dcost = cost_x - mincost_x;
  75.             y->dcost = cost_y - mincost_y;
  76.             x->dmin  = mincost_x;
  77.             y->dmin  = mincost_y - mincost_x;
  78.             if (a) a->dmin  = mincost_a - mincost_x;
  79.             if (b) b->dmin  = mincost_b - mincost_y;
  80.             if (c) c->dmin  = mincost_c - mincost_y;
  81.         }
  82.         else {
  83.             // x wurzel des rechten unterbaums (2)
  84.             a=y->left;
  85.             b=x->left;
  86.             c=x->right;
  87.             x->parent=0;
  88.             x->left=y;
  89.             y->parent=x;
  90.             y->right=b;
  91.             if (b) b->parent=y;
  92.             
  93.             x->successor=y->successor;
  94.             y->successor=0;
  95.             
  96.             mincost_a = (a) ? a->dmin + y->dmin : BIG;
  97.             mincost_b = (b) ? b->dmin + x->dmin + y->dmin : BIG;
  98.             mincost_c = (c) ? c->dmin + x->dmin + y->dmin : BIG;
  99.             mincost_x = x->dmin + y->dmin;
  100.             mincost_y = y->dmin;
  101.             cost_x    = x->dcost + mincost_x;
  102.             cost_y    = y->dcost + mincost_y;
  103.             
  104.             mincost_x = mincost_y;
  105.             mincost_y = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  106.             if (cost_y <= mincost_y) mincost_y = cost_y;
  107.             x->dcost = cost_x - mincost_x;
  108.             y->dcost = cost_y - mincost_y;
  109.             x->dmin  = mincost_x;
  110.             y->dmin  = mincost_y - mincost_x;
  111.             if (a) a->dmin  = mincost_a - mincost_y;
  112.             if (b) b->dmin  = mincost_b - mincost_y;
  113.             if (c) c->dmin  = mincost_c - mincost_x;           
  114.         }
  115.         continue;
  116.       }
  117.  
  118.       
  119.       // 2.Fall: x hat also Grossvater, x und parGenPtr(x) linke (rechte)
  120.       //           Soehne.
  121.       // Linke Soehne:
  122.  
  123.       if ((z->left==y)&&(y->left==x)){   //  (3)
  124.         a=x->left;
  125.         b=x->right;
  126.         c=y->right;
  127.         d=z->right;
  128.         y->left=b;
  129.         if (b) b->parent=y;
  130.         z->left=c;
  131.         if (c) c->parent=z;
  132.         x->right=y;
  133.         y->parent=x;
  134.         y->right=z;
  135.         z->parent=y;
  136.         if (zz) {
  137.             if (zz->left==z){
  138.              zz->left=x;
  139.             }
  140.             else{
  141.              zz->right=x;
  142.             }
  143.         }
  144.         else {     //  z is solid-tree-root
  145.             x->successor=z->successor;    
  146.             z->successor=0;
  147.         } 
  148.         x->parent=zz;
  149.         
  150.         mincost_a = (a) ? a->dmin + x->dmin + y->dmin + z->dmin : BIG;
  151.         mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  152.         mincost_c = (c) ? c->dmin + y->dmin + z->dmin : BIG;
  153.         mincost_d = (d) ? d->dmin + z->dmin : BIG;
  154.         mincost_x =     x->dmin + y->dmin + z->dmin;
  155.         mincost_y =     y->dmin + z->dmin;
  156.         mincost_z =     z->dmin;
  157.         cost_x     = mincost_x + x->dcost;
  158.         cost_y     = mincost_y + y->dcost;
  159.         cost_z     = mincost_z + z->dcost;
  160.         
  161.         mincost_x = mincost_z;
  162.         mincost_z = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  163.         if (cost_z <= mincost_z) mincost_z = cost_z;
  164.         mincost_y = (mincost_b <= mincost_z) ? mincost_b : mincost_z;
  165.         if (cost_y <= mincost_y) mincost_y = cost_y;
  166.         x->dcost = cost_x - mincost_x;
  167.         y->dcost = cost_y - mincost_y;
  168.         z->dcost = cost_z - mincost_z;
  169.         x->dmin = mincost_x;
  170.         y->dmin = mincost_y - mincost_x;
  171.         z->dmin = mincost_z - mincost_y;
  172.         if (a) a->dmin    = mincost_a - mincost_x;
  173.         if (b) b->dmin    = mincost_b - mincost_y;
  174.         if (c) c->dmin    = mincost_c - mincost_z;
  175.         if (d) d->dmin    = mincost_d - mincost_z;
  176.  
  177.         continue;
  178.       }
  179.  
  180.       
  181.       // Rechte Soehne:   (4)
  182.       
  183.       if ((z->right==y)&&(y->right==x)){
  184.         a=z->left;
  185.         b=y->left;
  186.         c=x->left;
  187.         d=x->right;
  188.         z->right=b;
  189.         if (b) b->parent=z;
  190.         z->parent=y;
  191.         y->left=z;
  192.         y->right=c;
  193.         if (c) c->parent=y;
  194.         y->parent=x;
  195.         x->left=y;
  196.         if (zz) {
  197.             if (zz->left==z){
  198.              zz->left=x;
  199.             }
  200.             else{
  201.              zz->right=x;
  202.             }
  203.         }
  204.         else { 
  205.             x->successor=z->successor;
  206.             z->successor=0;
  207.         }
  208.         x->parent=zz;
  209.         
  210.         mincost_a = (a) ? a->dmin + z->dmin : BIG;
  211.         mincost_b = (b) ? b->dmin + y->dmin + z->dmin : BIG;
  212.         mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  213.         mincost_d = (d) ? d->dmin + x->dmin + y->dmin + z->dmin : BIG;
  214.         mincost_x =     x->dmin + y->dmin + z->dmin;
  215.         mincost_y =     y->dmin + z->dmin;
  216.         mincost_z =     z->dmin;
  217.         cost_x     = mincost_x + x->dcost;
  218.         cost_y     = mincost_y + y->dcost;
  219.         cost_z     = mincost_z + z->dcost;
  220.         
  221.         mincost_x = mincost_z;
  222.         mincost_z = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  223.         if (cost_z <= mincost_z) mincost_z = cost_z;
  224.         mincost_y = (mincost_c <= mincost_z) ? mincost_c : mincost_z;
  225.         if (cost_y <= mincost_y) mincost_y = cost_y;
  226.         x->dcost = cost_x - mincost_x;
  227.         y->dcost = cost_y - mincost_y;
  228.         z->dcost = cost_z - mincost_z;
  229.         x->dmin = mincost_x;
  230.         y->dmin = mincost_y - mincost_x;
  231.         z->dmin = mincost_z - mincost_y;
  232.         if (a) a->dmin    = mincost_a - mincost_z;
  233.         if (b) b->dmin    = mincost_b - mincost_z;
  234.         if (c) c->dmin    = mincost_c - mincost_y;
  235.         if (d) d->dmin    = mincost_d - mincost_x;
  236.  
  237.         continue;
  238.       }
  239.       
  240.  
  241.       // 3.Fall: x linkes, p(x) rechtes Kind (oder umgekehrt)
  242.       // Zuerst x links, p(x) rechts:
  243.       
  244.       if ((z->right==y)&&(y->left==x)){   // (5)
  245.         a=z->left;
  246.         b=x->left;
  247.         c=x->right;
  248.         d=y->right;
  249.         z->right=b;
  250.         if (b) b->parent=z;
  251.         z->parent=x;
  252.         x->left=z;
  253.         y->left=c;
  254.         if (c) c->parent=y;
  255.         y->parent=x;
  256.         x->right=y;
  257.         if (zz) {
  258.             if (zz->left==z){
  259.              zz->left=x;
  260.             }
  261.             else{
  262.              zz->right=x;
  263.             }
  264.         } 
  265.         else {
  266.             x->successor=z->successor;
  267.             z->successor=0;
  268.         }
  269.         x->parent=zz;
  270.         
  271.         mincost_a = (a) ? a->dmin + z->dmin : BIG;
  272.         mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  273.         mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  274.         mincost_d = (d) ? d->dmin + y->dmin + z->dmin : BIG;
  275.         mincost_x =     x->dmin + y->dmin + z->dmin;
  276.         mincost_y =     y->dmin + z->dmin;
  277.         mincost_z =     z->dmin;
  278.         cost_x     = mincost_x + x->dcost;
  279.         cost_y     = mincost_y + y->dcost;
  280.         cost_z     = mincost_z + z->dcost;
  281.         
  282.         mincost_x = mincost_z;
  283.         mincost_z = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  284.         if (cost_z <= mincost_z) mincost_z = cost_z;
  285.         mincost_y = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  286.         if (cost_y <= mincost_y) mincost_y = cost_y;
  287.         x->dcost = cost_x - mincost_x;
  288.         y->dcost = cost_y - mincost_y;
  289.         z->dcost = cost_z - mincost_z;
  290.         x->dmin = mincost_x;
  291.         y->dmin = mincost_y - mincost_x;
  292.         z->dmin = mincost_z - mincost_x;
  293.         if (a) a->dmin    = mincost_a - mincost_z;
  294.         if (b) b->dmin    = mincost_b - mincost_z;
  295.         if (c) c->dmin    = mincost_c - mincost_y;
  296.         if (d) d->dmin    = mincost_d - mincost_y;
  297.  
  298.         continue;
  299.       }
  300.  
  301.       
  302.       // Nun x rechts, p(x) links:
  303.       
  304.       if ((z->left==y)&&(y->right==x)){    // (6)
  305.         a=y->left;
  306.         b=x->left;
  307.         c=x->right;
  308.         d=z->right;
  309.         y->right=b;
  310.         if (b) b->parent=y;
  311.         y->parent=x;
  312.         x->left=y;
  313.         z->left=c;
  314.         if (c) c->parent=z;
  315.         z->parent=x;
  316.         x->right=z;
  317.         if (zz) {
  318.             if (zz->left==z){
  319.              zz->left=x;
  320.             }
  321.             else{
  322.              zz->right=x;
  323.             }
  324.         }
  325.         else {
  326.             x->successor=z->successor;
  327.             z->successor=0;
  328.         }
  329.         x->parent=zz;
  330.         
  331.         mincost_a = (a) ? a->dmin + y->dmin + z->dmin : BIG;
  332.         mincost_b = (b) ? b->dmin + x->dmin + y->dmin + z->dmin : BIG;
  333.         mincost_c = (c) ? c->dmin + x->dmin + y->dmin + z->dmin : BIG;
  334.         mincost_d = (d) ? d->dmin + z->dmin : BIG;
  335.         mincost_x =     x->dmin + y->dmin + z->dmin;
  336.         mincost_y =     y->dmin + z->dmin;
  337.         mincost_z =     z->dmin;
  338.         cost_x     = mincost_x + x->dcost;
  339.         cost_y     = mincost_y + y->dcost;
  340.         cost_z     = mincost_z + z->dcost;
  341.         
  342.         mincost_x = mincost_z;
  343.         mincost_z = (mincost_c <= mincost_d) ? mincost_c : mincost_d;
  344.         if (cost_z <= mincost_z) mincost_z = cost_z;
  345.         mincost_y = (mincost_a <= mincost_b) ? mincost_a : mincost_b;
  346.         if (cost_y <= mincost_y) mincost_y = cost_y;
  347.         x->dcost = cost_x - mincost_x;
  348.         y->dcost = cost_y - mincost_y;
  349.         z->dcost = cost_z - mincost_z;
  350.         x->dmin = mincost_x;
  351.         y->dmin = mincost_y - mincost_x;
  352.         z->dmin = mincost_z - mincost_x;
  353.         if (a) a->dmin    = mincost_a - mincost_y;
  354.         if (b) b->dmin    = mincost_b - mincost_y;
  355.         if (c) c->dmin    = mincost_c - mincost_z;
  356.         if (d) d->dmin    = mincost_d - mincost_z;
  357.  
  358.       }
  359.      }
  360. }
  361.  
  362.  
  363. d_vertex dyna_trees::assemble(d_vertex u, d_vertex v, d_vertex w)
  364. {
  365.      double mincost_u,
  366.         mincost_v,
  367.         mincost_w,
  368.         cost_v;
  369.  
  370.      v->left=u;
  371.      v->right=w;
  372.      if (u) u->parent=v;
  373.      if (w) w->parent=v;
  374.      
  375.      mincost_u = (u) ? u->dmin : BIG;
  376.      mincost_v =       v->dmin;
  377.      mincost_w = (w) ? w->dmin : BIG;
  378.      cost_v = mincost_v + v->dcost;
  379.      
  380.      mincost_v = (mincost_u <= mincost_w) ? mincost_u : mincost_w;
  381.      if (cost_v < mincost_v) mincost_v = cost_v;
  382.      v->dcost = cost_v - mincost_v;
  383.      v->dmin = mincost_v;
  384.      if (u) u->dmin = mincost_u - mincost_v;
  385.      if (w) w->dmin = mincost_w - mincost_v;
  386.  
  387.      return v;
  388. }
  389.  
  390.  
  391. void   dyna_trees::disassemble(d_vertex v, d_vertex& v1, d_vertex& v2) {
  392.      double mincost_v1,
  393.         mincost_v2;
  394.  
  395.  
  396.      v1=v->left;
  397.      v2=v->right;
  398.      if (v1) v1->parent=0;
  399.      if (v2) v2->parent=0;
  400.      v->left=0;
  401.      v->right=0;
  402.  
  403.      mincost_v1 = (v1) ? v1->dmin + v->dmin : BIG;
  404.      mincost_v2 = (v2) ? v2->dmin + v->dmin : BIG;
  405.  
  406.      if (v1) v1->dmin = mincost_v1;
  407.      if (v2) v2->dmin = mincost_v2;
  408.      
  409.      v->dmin += v->dcost;
  410.      v->dcost = 0;
  411. }
  412.  
  413.  
  414. d_vertex dyna_trees::makepath(void* i)
  415. {
  416.      if (first==0) {
  417.       first=last=new d_node(i);
  418.      }
  419.      else {
  420.       last->next=new d_node(i);
  421.       last=last->next;
  422.      }
  423.      return last;
  424. }
  425.  
  426.  
  427. d_vertex dyna_trees::findpath(d_vertex v)
  428. {
  429.      splay(v);
  430.      return v;
  431. }
  432.  
  433.  
  434.  
  435. d_vertex dyna_trees::findpathcost(d_path p, double& d)
  436. {
  437.      d_vertex w;
  438.      w=p;
  439.      
  440.      while( !( (w->dcost==0) && ( (w->right==0)||(w->right->dmin>0) ) ) ) {
  441.       if (w->right) {
  442.         if (w->right->dmin == 0) {
  443.              w=w->right;
  444.         } else {
  445.              if (w->dcost>0) w=w->left;
  446.         }  
  447.       }
  448.       else {
  449.         if (w->dcost>0) w=w->left;
  450.       }
  451.      }
  452.      splay(w);
  453.      d=w->dmin;
  454.      return w;
  455. }
  456.  
  457.  
  458.  
  459. d_vertex dyna_trees::findtail(d_path p)
  460. {
  461.      d_vertex w;
  462.      w=p;
  463.      
  464.      while(w->right) {
  465.       w=w->right;
  466.      }
  467.      splay(w);
  468.      return w;
  469. }
  470.  
  471.  
  472.  
  473. void dyna_trees::addpathcost(d_path p, double x)
  474. {
  475.      p->dmin += x;
  476. }
  477.  
  478.  
  479.  
  480. d_vertex dyna_trees::join(d_path p, d_path v, d_path q)
  481. {
  482.      return assemble(p, v, q);
  483. }
  484.  
  485.  
  486.  
  487. void dyna_trees::split(d_vertex v, d_vertex& v1, d_vertex& v2)
  488. {
  489.      splay(v);
  490.      disassemble(v, v1, v2);
  491. }
  492.  
  493.  
  494.  
  495. d_path dyna_trees::expose(d_vertex v)
  496. {
  497.      d_path   p,
  498.           q,
  499.           r;
  500.      d_vertex w;
  501.      
  502.      p=0;
  503.      while (v) {
  504.       w=findpath(v)->successor;
  505.       split(v,q,r);
  506.       if (q) q->successor=v;
  507.       p=join(p, v, r);
  508.       v=w;
  509.      }
  510.      p->successor=0;
  511.      return p;
  512. }
  513.  
  514.  
  515. d_vertex dyna_trees::maketree(void* i)
  516. {
  517.      copy_inf(i);
  518.  
  519.      d_vertex v;
  520.      v=makepath(i);
  521.      v->successor=0;
  522.      return v;
  523. }
  524.  
  525.  
  526. d_vertex dyna_trees::findroot(d_vertex v)
  527. {
  528.      return findtail(expose(v));
  529. }
  530.  
  531.  
  532.  
  533. d_vertex dyna_trees::findcost(d_vertex v, double& d)
  534. {
  535.      return findpathcost(expose(v),d);
  536. }
  537.  
  538.  
  539.  
  540. void dyna_trees::addcost(d_vertex v, double x)
  541. {
  542.      addpathcost(expose(v),x);
  543. }
  544.  
  545.  
  546.  
  547. void dyna_trees::link(d_vertex v, d_vertex w)
  548. {
  549.      join( (d_vertex) 0, expose(v), expose(w) )->successor=0;
  550. }
  551.  
  552.  
  553.  
  554. void dyna_trees::cut(d_vertex v) 
  555. {
  556.      d_path p,q;
  557.      
  558.      expose(v);
  559.      split(v,p,q);
  560.      v->successor=q->successor=0;
  561. }
  562.  
  563.  
  564.  
  565. dyna_trees::~dyna_trees()
  566. {
  567.      d_node *x, 
  568.         *y;
  569.       
  570.      x=first;
  571.      while(x) {
  572.       y=x->next;
  573.       delete x;
  574.       x=y;
  575.      }
  576. }
  577.  
  578.  
  579.  
  580.